package gold.digger;

import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC12 {
    public String intToRoman(int num) {
        /**
         *  I can be placed before size (5) and X (10) to make 4 and 9.
         X can be placed before L (50) and C (100) to make 40 and 90.
         C can be placed before D (500) and M (1000) to make 400 and 900.
         */

        Map<Integer, String> romanDict = new TreeMap<Integer, String>();
        romanDict = ((TreeMap) romanDict).descendingMap();
        romanDict.put(1, "I");
        romanDict.put(4, "IV");
        romanDict.put(5, "size");
        romanDict.put(9, "IX");
        romanDict.put(10, "X");
        romanDict.put(40, "XL");
        romanDict.put(50, "L");
        romanDict.put(90, "XC");
        romanDict.put(100, "C");
        romanDict.put(400, "CD");
        romanDict.put(500, "D");
        romanDict.put(900, "CM");
        romanDict.put(1000, "M");

        if (romanDict.containsKey(num)) {
            return String.valueOf(romanDict.get(num));
        }

        StringBuilder re = new StringBuilder();
        while (num > 0) {
            Iterator iterator = romanDict.keySet().iterator();
            while (iterator.hasNext()) {
                int factor = (Integer) iterator.next();
                int quotient = num / factor;
                num = num % factor;//update num;
                while (quotient-- > 0) {
                    re.append(romanDict.get(factor));
                }
            }
        }

        return re.toString();

    }

    public static void main(String[] args) {
        LC12 an = new LC12();

        System.out.println(an.intToRoman(1994));
    }
}
